// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-27 16:18
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.Arrays;
import java.util.TreeSet;

public class MaxSumSubmatrix {
    /**
     * 矩形区域不超过k值的最大数值和
     */
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length, ans = Integer.MIN_VALUE;
        boolean isRight = n > m;
        for (int top = 1; top <= (isRight ? m : n); top++) {
            int[] sum = new int[(isRight ? n : m) + 1];
            Arrays.fill(sum, 0);
            for (int bot = top; bot <= (isRight ? m : n); bot++) {
                int a = 0;
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                for (int fixed = 1; fixed <= (isRight ? n : m); fixed++) {
                    sum[fixed] += isRight ? mat[bot - 1][fixed - 1] : mat[fixed - 1][bot - 1];
                    a += sum[fixed];
                    Integer ceiling = set.ceiling(a - k);
                    if (ceiling != null) {
                        // 存在不固定边界的子矩阵
                        ans = Math.max(a - ceiling, ans);
                    }
                    set.add(a);
                }
            }
        }
        return ans;
    }
}
